﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace text
{
    public class HuangHou
    {
        public HuangHou()
        {
            board = new List<List<string>>();
        }
        public List<List<string>> board;
        private List<string> charToString(char[][] array)
        {
            List<string> result = new List<string>();
            foreach (char[] chars in array)
            {
                result.Add(new string(chars));
            }
            return result;
        }
        public List<List<string>> solveNQueens(int n)
        {
            char[][] res = new char[n][];
            for (int i = 0; i < n; i++)
            {
                res[i] = new char[n];
                for (int j = 0; j < n; j++)
                {
                    res[i][j] = '.';
                }
            }
            backtrack(res, 0);
            return board;
        }
        public void backtrack(char[][] res, int row)
        {
            int n= res.GetLength(0);//总的行数
            //触发结束条件
            if (row==n)
            {
                board.Add(charToString(res));
                return ;
            }
            for (int col = 0; col < n; col++)
            {
                if (!isValid(res, row, col))
                    continue;
                // 做选择
                res[row][col] = 'Q';
                // 进入下一行决策
                backtrack(res, row + 1);
                // 撤销选择
                res[row][col] = '.';
            }

        }
        /// <summary>
        /// 判断当前行,列是否符合规则
        /// </summary>
        /// <param name="board"></param>
        /// <param name="row"></param>
        /// <param name="col"></param>
        /// <returns></returns>
        public bool isValid(char[][] board,int row,int col)
        {
            try
            {
                int n = board.Length;//获取列数
                //判断列
                for (int i = 0; i < row; i++)
                {
                    if (board[i][col] == 'Q')
                        return false;
                }//判断左上角
                //for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
                //{
                //    if (board[i, j] == 'Q')
                //        return false;
                //}//判断右上角
                //for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j--)
                //{
                //    if (board[i, j] == 'Q')
                //        return false;
                //}
                // 检查右上方是否有皇后互相冲突
                for (int i = row - 1, j = col + 1;
                        i >= 0 && j < n; i--, j++)
                {
                    if (board[i][j] == 'Q')
                        return false;
                }
                // 检查左上方是否有皇后互相冲突
                for (int i = row - 1, j = col - 1;
                        i >= 0 && j >= 0; i--, j--)
                {
                    if (board[i][j] == 'Q')
                        return false;
                }
                return true;
            }
            catch (Exception)
            {
                return false;
                throw;
            }
            
        }
    }
}
